A parallel computer system is known, in which a job scheduler performs the scheduling for previously allocating a plurality of jobs to calculation resources, and the jobs allocated to the calculation resources are sequentially executed. FIG. 1 illustrates a flow of general job allocation performed by a job scheduler, and FIG. 2 illustrates a flow chart illustrating a flow of a “job selection” process and a “calculation resource selection” process.
The job allocation is performed as follows. As illustrated in FIG. 1, the job scheduler accepts jobs submitted by respective users in a “job acceptance” process. The job scheduler coordinates the submitted jobs at constant intervals, and the job scheduler executes the job selection process.
In the job selection process, at first, the job scheduler rearranges (sorts) all of the plurality of jobs (jobs waiting for execution) as targets of the job selection process in accordance with predetermined priorities (for example, the fair-ware control and the group priority control) (1 in FIG. 2). Subsequently, the job scheduler takes out the job disposed at the head from a sorted job sequence, and the job is set to a variable “JOB” (2 in FIG. 2). Subsequently, the job scheduler calls a subroutine for the calculation resource selection process so that the calculation resource is allocated to the job set to the variable “JOB” (3 in FIG. 2).
In the calculation resource selection process, any calculation resource in a vacant state (vacant resource) is searched in accordance with the required quantity of the job (for example, the number of calculation node or nodes required to execute the job, the shape of the calculation node, and the required time for execution of the job (limiting value of the elapsed time)), and the job is allocated to the calculation resource. The calculation resource selection process is executed for all of the jobs which form the job sequence (see the loop of 4 in FIG. 2). Each of the jobs, to which the calculation resource is allocated, is executed by using the allocated calculation resource, if the current time becomes the scheduled start time (“JOB EXECUTION” in FIG. 1).
The situation of allocation of the calculation resources with respect to the respective jobs can be expressed by a scheduling map M as illustrated in FIG. 1. In the scheduling map M, for example, the vertical axis represents the axis of the calculation resource, and the horizontal axis represents the time axis, wherein the line segments in the horizontal direction, which form the lattice of the calculation resource and the time, indicate the unit time, and the line segments in the vertical direction indicate the unit of the calculation resource. The unit of the calculation resource is referred to as “calculation node”. The calculation node is formed by a single processor (for example, CPU) or a plurality of processors (processor group).
The respective jobs waiting for execution are allocated one by one to the calculation resource so that the execution is successively started in an order starting from those having high priorities in accordance with the job selection process and the calculation resource selection process described above. However, the job (backfill job), which is the target of the backfill scheduling, is allocated to the calculation resource while overtaking the jobs having high priorities within a range in which the execution start is not disturbed for the jobs having priorities higher than that of the job.
For more information, see Japanese Patent Laid-Open Publication No. 07-141305, Japanese Patent Laid-Open Publication No. 2008-107875, and Japanese Patent Laid-Open Publication No. 2006-146864.